Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи №3(4) з курсу „ Дослідження комп'ютерних систем штучного інтелекту ” Тема: Застосування генетичних алгоритмів для вирішення задачі комівояжера Виконав: ст. гр. КСМм-1 Львів – 2007 Мета: ознайомитись з методами вирішення задач за допомогою генетичних алгоритмів та використати даний алгоритм для вирішення задачі комівояжера. Теоретичні відомості Задача комівояжера у стандартній постановці виглядає так: є набір міст, потрібно відвідати найкоротшим шляхом всі міста, але кожне місто відвідується лише раз і повернутись до відправного пункту. Формально TSP можна вирішити наступним чином: Даними є: натуральні числа n ≥ 3 i маршрут C =(cij), де cij - ітераційний підрахунок, що циклічно змінюється. EMBED Equation.3
 TSP є відносно старою проблемою. Вперше вона була сформульована Ейлером в 1759 році (але під іншою назвою), якій хотів розв”язати проблему шахового коня. Правильне розв”язання повинно містити шлях шахового коня по всіх 64 шахових клітинах, так щоб на кожній клітині поля кінь побував лише один раз. Термін ‘travelling salesman’ вперше був застосований в 1932 році у німецькій книзі, присвяченій вирішенню задачі комівояжера. Після багатьох років, проблема комівояжера дочекалась на багато способів розв”язання. Існує декілька причин цього. По перше TSP є дуже простим в описуванні, але важким у розв’язанні. Не знаємо жодного алгоритму, що розв’язує це завдання миттєво в баготовимірному часі. Цей недолік алгоритму, що розв’язує завдання багатовимірному часі є характерним для проблем, відомих під назвою NP – повних, для яких проблема комівояжера є класичним прикладом. По друге, TSP має застосування в багатьох різних проблемах, що зачіпають різного роду шляхи і пункти. По трете, по мірі отримання багато інформації на тему проблеми комівояжера, згодом її можна використовувати як свого роду тестову задачу, нові комбанаторні методи часто тестуються на TSP, з метою переконання в їх приктичній здатності. І зрештою велика кількість проблем, в яких маємо відповідно до завдань штучного інтелекту, призводять до знаходження найкращої permutacji n елементів. Представлення і оператори Відомо багато різних способів представлення здатних до розв”язування проблеми комівояжера за допомогою генетичних алгоритмів. Деякі з них як бінарі рішення чи маршрутне рішення використовують бінарні значення для представлення даного шляху. Хоча таке рішення є стандартом в світі генетичних алгоритмів, однак для задачі комівояжера проблемою є те, що оператори схрещуваня і мутації можуть давати погані наслідки. Для того мусимо залишити сформульовані оператори виправлень. Найкращим природнім способом представлення шляху є вигляд представлення. В цьому представленні n міст, які мають розмістити пункти відвідувань в n-елементний ланцюжок таким чином, що якщо і-те місто знаходиться в j-ій позиції за рахунком, це означає, що і-те місто відвідане як j-те. Таке представлення дозволяє сформулювати велику кількість різних операторів схрещування і мутації. Можна стверджувати, що на даний час більшість генетичних алгоритмів, що заходять приблизне розв”язання задачі комівояжера вживають таке представлення. Вагомою причиною для того є інтуїтивна простота і природність представлення, а також добрі наслідки, отримані при його застосуванні Бінарне представлення В бінарному представленні задачі комівояжера для n-міст, кожне місто закодовано у ланцюжок довжиною [log2 n] бітів. Одиночне рішення зрештою є ланцюжком, довжиною n*[log2 n] бітів. Наприклад, при шістьох містах кожне місто представлено ланцюжком довжиною у 3 біти Шлях 1-2-3-4-5-6 представлятиметься: 000 001 010 011 100 101 Зауважимо, що існують 3-бітові ланцюжки. З них не кодують жодного міста: 110 і 111 Класичне схрещування (Classical Crossover) Оператор класичного схрещування був запропонований Голандом (1975). ...